home *** CD-ROM | disk | FTP | other *** search
/ SPACE 1 / SPACE - Library 1 - Volume 1.iso / program / 441 / dlibs12 / hsort.c < prev    next >
C/C++ Source or Header  |  1990-11-23  |  3KB  |  167 lines
  1. /*
  2.  *    Heap sorting functions
  3.  */
  4.  
  5. static _wsift(base, i, n, cmp)
  6.     register int *base;
  7.     register int i;
  8.     register int n;
  9.     register int (*cmp)();
  10.     {
  11.     register int j, t;
  12.  
  13.     while((j = ((i << 1) + 1)) < n)
  14.         {
  15.         if((j < (n - 1)) && ((*cmp)((base+j), (base+j+1)) < 0))
  16.             ++j;
  17.         if((*cmp)((base+i), (base+j)) < 0)
  18.             {
  19.             t = base[i];
  20.             base[i] = base[j];
  21.             base[j] = t;
  22.             i = j;
  23.             }
  24.         else
  25.             break;
  26.         }
  27.     }
  28.  
  29. static _whsort(base, num, cmp)
  30.     register int *base;
  31.     register int num;
  32.     register int (*cmp)();
  33.     {
  34.     register int i, j;
  35.  
  36.     for(i = ((num >> 1) - 1); (i > 0); --i)
  37.         _wsift(base, i, num, cmp);
  38.     i = num;
  39.     while(i > 1)
  40.         {
  41.         _wsift(base, 0, i--, cmp);
  42.         j = *base;
  43.         *base = *(base + i);
  44.         *(base + i) = j;
  45.         }
  46.     }
  47.  
  48. static _lsift(base, i, n, cmp)
  49.     register long *base;
  50.     register int i;
  51.     register int n;
  52.     register int (*cmp)();
  53.     {
  54.     register int j;
  55.     register long t;
  56.  
  57.     while((j = ((i << 1) + 1)) < n)
  58.         {
  59.         if((j < (n - 1)) && ((*cmp)((base+j), (base+j+1)) < 0))
  60.             ++j;
  61.         if((*cmp)((base+i), (base+j)) < 0)
  62.             {
  63.             t = base[i];
  64.             base[i] = base[j];
  65.             base[j] = t;
  66.             i = j;
  67.             }
  68.         else
  69.             break;
  70.         }
  71.     }
  72.  
  73. static _lhsort(base, num, cmp)
  74.     register long *base;
  75.     register int num;
  76.     register int (*cmp)();
  77.     {
  78.     register int i;
  79.     register long j;
  80.  
  81.     for(i = ((num >> 1) - 1); (i > 0); --i)
  82.         _lsift(base, i, num, cmp);
  83.     i = num;
  84.     while(i > 1)
  85.         {
  86.         _lsift(base, 0, i--, cmp);
  87.         j = *base;
  88.         *base = *(base + i);
  89.         *(base + i) = j;
  90.         }
  91.     }
  92.  
  93. static _nswap(pa, pb, n)
  94.     register char *pa;
  95.     register char *pb;
  96.     register int n;
  97.     {
  98.     register char c;
  99.  
  100.     while(n--)
  101.         {
  102.         c = *pa;
  103.         *pa++ = *pb;
  104.         *pb++ = c;
  105.         }
  106.     }
  107.  
  108. static _nsift(base, i, n, size, cmp)
  109.     register char *base;
  110.     register int i;
  111.     register int n;
  112.     register int size;
  113.     register int (*cmp)();
  114.     {
  115.     register int j;
  116.     register char *p;
  117.  
  118.     while((j = ((i << 1) + 1)) < n)
  119.         {
  120.         p = (base+size*j);
  121.         if((j < (n - 1)) && ((*cmp)(p, p+size) < 0))
  122.             {
  123.             ++j;
  124.             p += size;
  125.             }
  126.         if((*cmp)((base+size*i), p) < 0)
  127.             {
  128.             _nswap((base+size*i), p, size);
  129.             i = j;
  130.             }
  131.         else
  132.             break;
  133.         }
  134.     }
  135.  
  136. static _nhsort(base, num, size, cmp)
  137.     register char *base;
  138.     register int num;
  139.     register int size;
  140.     register int (*cmp)();
  141.     {
  142.     register int i, j;
  143.  
  144.     for(i = ((num >> 1) - 1); (i > 0); --i)
  145.         _nsift(base, i, num, size, cmp);
  146.     i = num;
  147.     while(i > 1)
  148.         {
  149.         _nsift(base, 0, i--, size, cmp);
  150.         _nswap(base, (base+size*i), size);
  151.         }
  152.     }
  153.  
  154. hsort(base, num, size, cmp)
  155.     char *base;
  156.     int num;
  157.     int size;
  158.     int (*cmp)();
  159.     {
  160.     if(size == 2)
  161.         _whsort(base, num, cmp);
  162.     else if(size == 4)
  163.         _lhsort(base, num, cmp);
  164.     else
  165.         _nhsort(base, num, size, cmp);
  166.     }
  167.